PsL Monthly 1993 December

home *** CD-ROM | disk | FTP | other *** search

/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / basic / sorts.bas < prev next >

Wrap

BASIC Source File | 1992-06-17 | 19.5 KB | 445 lines

10 COLOR 14, 1: CLS : 'Filename: sorts.bas. 1992. Earle Arnow 15 GOSUB 6000 20 CLS : CLEAR : RANDOMIZE TIMER 30 LOCATE 9, 11: PRINT "MENU 2": PRINT TAB(9); STRING$(62, "-") 40 PRINT TAB(10); "1. Bubblesort"; TAB(36); "2. Endsort" 50 PRINT TAB(10); "3. Quicksort"; TAB(36); "4. Stripped Quicksort" 60 PRINT TAB(10); "5. Jumpsort"; TAB(36); "6. Flipsort" 70 PRINT TAB(10); "7. Fastsort"; TAB(36); "8. Insertion Sort" 80 PRINT TAB(10); "9. Shell-Metzner Sort"; TAB(35); "10. Smsort (Rewritten Shell-Metzner)" 90 PRINT TAB(9); "11. Run all sorts"; TAB(35); "12. Return to Menu 1" 100 PRINT 110 LOCATE 19, 10: INPUT "<ENTER> a number ===> ", NN 120 IF NN < 1 OR NN > 12 THEN LOCATE 19, 10: PRINT STRING$(30, " "): GOTO 110 125 IF NN = 12 THEN 700 130 CLS : LOCATE 9, 21: INPUT "Length of the array ", N 140 DIM A(N), A1(N), A2(N), S(50), A$(N), A1$(N), A2$(N) 145 IF S = 1 THEN 8000 150 CLS : PRINT "Unsorted array:": FOR Y = 1 TO N: R = INT(RND * N): A(Y) = R: PRINT A(Y); : A1(Y) = R: NEXT Y: PRINT "" 160 ON NN GOTO 200, 240, 270, 300, 330, 360, 390, 420, 450, 480, 600 200 T1 = TIMER: GOSUB 1000: T2 = TIMER: SEC1 = T2 - T1: PRINT "Bubblesort:": GOSUB 900 210 IF ZZ THEN GOSUB 920: GOTO 240 220 PRINT : PRINT TAB(20); "Bubblesort:"; SEC1; "seconds": GOTO 940 240 T1 = TIMER: GOSUB 1500: T2 = TIMER: SEC2 = T2 - T1: PRINT "Endsort:": GOSUB 900 250 IF ZZ THEN GOSUB 920: GOTO 270 260 PRINT : PRINT TAB(20); "Endsort:"; SEC2; "seconds": GOTO 940 270 T1 = TIMER: GOSUB 2000: T2 = TIMER: SEC3 = T2 - T1: PRINT "Quicksort:": GOSUB 900 280 IF ZZ THEN GOSUB 920: GOTO 300 290 PRINT : PRINT TAB(20); "Quicksort:"; SEC3; "seconds": GOTO 940 300 T1 = TIMER: GOSUB 2500: T2 = TIMER: SEC4 = T2 - T1: PRINT "Stripped quicksort:": GOSUB 900 310 IF ZZ THEN GOSUB 920: GOTO 330 320 PRINT : PRINT TAB(20); "Stripped quicksort:"; SEC4; "seconds": GOTO 940 330 T1 = TIMER: GOSUB 3000: T2 = TIMER: SEC5 = T2 - T1: PRINT "Jumpsort:": GOSUB 900 340 IF ZZ THEN GOSUB 920: GOTO 360 350 PRINT : PRINT TAB(20); "Jumpsort:"; SEC5; "seconds": GOTO 940 360 T1 = TIMER: GOSUB 3500: T2 = TIMER: SEC6 = T2 - T1: PRINT "Flipsort:": GOSUB 900 370 IF ZZ THEN GOSUB 920: GOTO 390 380 PRINT : PRINT TAB(20); "Flipsort:"; SEC6; "seconds": GOTO 940 390 T1 = TIMER: GOSUB 4000: T2 = TIMER: SEC7 = T2 - T1: PRINT "Fastsort:": GOSUB 900 400 IF ZZ THEN GOSUB 920: GOTO 420 410 PRINT : PRINT TAB(20); "Fastsort:"; SEC7; "seconds": GOTO 940 420 T1 = TIMER: GOSUB 4500: T2 = TIMER: SEC8 = T2 - T1: PRINT "Insertion sort:": GOSUB 900 430 IF ZZ THEN GOSUB 920: GOTO 450 440 PRINT : PRINT TAB(20); "Insertion sort:"; SEC8; "seconds": GOTO 940 450 T1 = TIMER: GOSUB 5000: T2 = TIMER: SEC9 = T2 - T1: PRINT "Shell-Metzner sort:": GOSUB 900 460 IF ZZ THEN GOSUB 920: GOTO 480 470 PRINT : PRINT TAB(20); "Shell-Metzner sort:"; SEC9; "seconds": GOTO 940 480 T1 = TIMER: GOSUB 5500: T2 = TIMER: SEC10 = T2 - T1: PRINT "smsort (rewritten Shell-Metzner):": GOSUB 900 490 IF ZZ THEN GOSUB 920: GOTO 510 500 PRINT : PRINT TAB(20); "Smsort (rewritten Shell-Metzner):"; SEC10; "seconds": GOTO 940 510 PRINT : PRINT "Bubblesort:"; SEC1; "seconds"; TAB(40); "Endsort:"; SEC2; "seconds" 520 PRINT "Quicksort:"; SEC3; "seconds"; TAB(40); "Stripped quicksort:"; SEC4; "seconds" 540 PRINT "Jumpsort:"; SEC5; "seconds"; TAB(40); "Flipsort:"; SEC6; "seconds" 550 PRINT "Fastsort:"; SEC7; "seconds"; TAB(40); "Insertion sort:"; SEC8; "seconds" 560 PRINT "Shell-Metzner sort:"; SEC9; "seconds"; TAB(40); "Smsort:"; SEC10; "seconds" 570 GOTO 940 600 ZZ = 1: GOTO 200 700 GOTO 10 890 '*** print sorted array 900 FOR Y = 1 TO N: PRINT A(Y); : NEXT Y: PRINT "" 910 RETURN 915 '*** Restore unsorted array 920 FOR Y = 1 TO N: A(Y) = A1(Y): NEXT Y: RETURN 940 PRINT : PRINT TAB(20); "Press any key to return to the MENU" 950 I$ = INPUT$(1): RUN 990 '*** Bubblesort 1000 F = 0 1010 FOR Y = 1 TO N - 1 1020 IF A(Y) > A(Y + 1) THEN SWAP A(Y), A(Y + 1): F = 1 1030 NEXT Y 1040 IF F = 0 THEN RETURN ELSE F = 0: GOTO 1010 1490 '*** endsort 1500 EN = N + 1 1510 EN = EN - 1 1520 IF EN = 1 THEN RETURN 1530 FOR Y = 1 TO EN - 1 1540 IF A(Y) > A(EN) THEN SWAP A(Y), A(EN) 1550 NEXT Y 1560 GOTO 1510 1990 '*** quicksort 2000 K8 = 0: I8 = 0 2010 S(I8 + 1) = 1: S(I8 + 2) = N 2020 K8 = K8 + 1 2030 IF K8 = 0 THEN RETURN 2040 K8 = K8 - 1: I8 = K8 + K8 2050 A8 = S(I8 + 1): B8 = S(I8 + 2) 2060 Z8 = A(A8): U8 = A8: L8 = B8 + 1 2070 L8 = L8 - 1 2080 IF L8 = U8 THEN 2130 2090 IF Z8 <= A(L8) THEN 2070 ELSE A(U8) = A(L8) 2100 U8 = U8 + 1 2110 IF L8 = U8 THEN 2130 2120 IF Z8 >= A(U8) THEN 2100 ELSE A(L8) = A(U8): GOTO 2070 2130 A(U8) = Z8 2140 IF B8 - U8 >= 2 THEN I8 = K8 + K8: S(I8 + 1) = U8 + 1: S(I8 + 2) = B8: K8 = K8 + 1 2150 IF L8 - A8 >= 2 THEN I8 = K8 + K8: S(I8 + 1) = A8: S(I8 + 2) = L8 - 1: K8 = K8 + 1 2160 GOTO 2030 2490 '*** stripped quicksort 2500 K8 = 0 2510 S1(K8) = 1: S2(K8) = N 2520 K8 = K8 + 1 2530 IF K8 = 0 THEN RETURN 2540 K8 = K8 - 1 2550 A8 = S1(K8): B8 = S2(K8) 2560 Z8 = A(A8): U8 = A8: L8 = B8 + 1 2570 L8 = L8 - 1 2580 IF L8 = U8 THEN 2630 2590 IF Z8 <= A(L8) THEN 2570 ELSE A(U8) = A(L8) 2600 U8 = U8 + 1 2610 IF L8 = U8 THEN 2630 2620 IF Z8 >= A(U8) THEN 2600 ELSE A(L8) = A(U8): GOTO 2570 2630 A(U8) = Z8 2640 IF B8 - U8 >= 2 THEN S1(K8) = U8 + 1: S2(K8) = B8: K8 = K8 + 1 2650 IF L8 - A8 >= 2 THEN S1(K8) = A8: S2(K8) = L8 - 1: K8 = K8 + 1 2660 GOTO 2530 2990 '*** jumpsort 3000 K8 = 0 3010 S1(K8) = 1: S2(K8) = N 3020 K8 = K8 + 1 3030 IF K8 = 0 THEN RETURN 3040 K8 = K8 - 1 3050 A8 = S1(K8): B8 = S2(K8) 3060 Z8 = A(A8): U8 = A8: L8 = B8 + 1 3070 L8 = L8 - 1 3080 IF L8 = U8 THEN 3130 3090 IF Z8 <= A(L8) THEN 3070 ELSE SWAP A(U8), A(L8) 3100 U8 = U8 + 1 3110 IF L8 = U8 THEN 3130 3120 IF Z8 >= A(U8) THEN 3100 ELSE SWAP A(L8), A(U8): GOTO 3070 3130 IF B8 - U8 >= 2 THEN S1(K8) = U8 + 1: S2(K8) = B8: K8 = K8 + 1 3140 IF L8 - A8 >= 2 THEN S1(K8) = A8: S2(K8) = L8 - 1: K8 = K8 + 1 3150 GOTO 3030 3490 '*** flipsort 3500 C = 0 3510 B1(C) = 1: B2(C) = N 3520 C = 1 3530 IF C = 0 THEN RETURN 3540 C = C - 1: D = B1(C): E = B2(C) 3550 F = D - 1: G = E 3560 F = F + 1 3570 IF F = G THEN 3620 3580 IF A(F) > A(G) THEN SWAP A(F), A(G) ELSE 3560 3590 G = G - 1 3600 IF F = G THEN 3620 3610 IF A(G) < A(F) THEN SWAP A(G), A(F): GOTO 3560 ELSE 3590 3620 IF E - F >= 2 THEN B1(C) = F + 1: B2(C) = E: C = C + 1 3630 IF G - D >= 2 THEN B1(C) = D: B2(C) = G - 1: C = C + 1 3640 GOTO 3530 3990 '*** fastsort 4000 C = 0 4010 B1(C) = 1: B2(C) = N 4020 C = C + 1 4030 IF C = 0 THEN RETURN 4040 C = C - 1 4050 D = B1(C): E = B2(C) 4060 Z = A(D): F = D - 1: G = E + 1 4070 FOR Y = D TO E 4080 IF Z > A(Y) THEN F = F + 1: A(F) = A(Y) 4090 IF Z < A(Y) THEN G = G - 1: A2(G) = A(Y) 4100 NEXT Y 4110 FOR Y = G TO E: A(Y) = A2(Y): NEXT Y 4120 FOR Y = F + 1 TO G - 1: A(Y) = Z: NEXT Y 4130 IF F - D > 0 THEN B1(C) = D: B2(C) = F: C = C + 1 4140 IF E - G > 0 THEN B1(C) = G: B2(C) = E: C = C + 1 4150 GOTO 4030 4490 '*** insertion sort 4500 FOR Y = 1 TO N - 1 4510 IF A(Y) > A(Y + 1) THEN SWAP A(Y), A(Y + 1) ELSE 4550 4520 D = Y - 1: IF D < 1 THEN 4550 4530 IF A(D) > A(D + 1) THEN SWAP A(D), A(D + 1) ELSE 4550 4540 D = D - 1: IF D >= 1 THEN 4530 4550 NEXT Y 4560 RETURN 4990 '*** Shell-Metzner sort 5000 M = N 5010 M = INT(M / 2) 5020 IF M = 0 THEN RETURN 5030 K = N - M: J = 1 5040 I = J 5050 L = I + M 5060 IF A(I) <= A(L) THEN 5100 5070 SWAP A(I), A(L): I = I - M 5090 IF I >= 1 THEN 5050 5100 J = J + 1 5110 IF J <= K THEN 5040 ELSE 5010 5490 '*** smsort (rewritten Shell-Metzner) 5500 M = N 5510 M = INT(M / 2): K = N - M 5520 IF M = 0 THEN RETURN 5530 FOR Y = 1 TO K 5540 IF A(Y) > A(Y + M) THEN SWAP A(Y), A(Y + M) ELSE 5580 5550 D = Y - M: IF D < 1 THEN 5580 5560 IF A(D) > A(D + M) THEN SWAP A(D), A(D + M) ELSE 5580 5570 D = D - M: IF D >= 1 THEN 5560 5580 NEXT Y 5590 GOTO 5510 5900 ' 5995 'Menu 1 5997 ' 6000 LOCATE 8, 20: PRINT "MENU 1": LOCATE 10, 20: PRINT "1. Discussion of sort methods": LOCATE 11, 20: PRINT "2. Run the sort programs": LOCATE 12, 20: PRINT "3. Exit to DOS" 6020 IN$ = INKEY$: IF IN$ = "1" THEN 7000 ELSE IF IN$ = "2" THEN CLS : GOTO 6100 ELSE IF IN$ = "3" THEN COLOR 7, 0: CLS:SYSTEM ELSE 6020 6100 CLS : LOCATE 8, 20: PRINT "Type of array:" 6120 LOCATE 10, 20: PRINT "1. Numerical" 6140 LOCATE 11, 20: PRINT "2. String" 6160 LOCATE 13, 20: PRINT "<ENTER> 1 or 2" 6180 IN$ = INKEY$: IF IN$ = "1" THEN 30 ELSE IF IN$ = "2" THEN S = 1: GOTO 30 ELSE 6180 6985 ' 6990 'Discussion 6995 ' 7000 CLS : LOCATE 2, 1: PRINT "BRIEF DISCUSSION OF SORTING PROGRAMS": PRINT 7020 PRINT "The sort routines used in writing programs in BASIC can be grouped into three" 7040 PRINT "types. The first type involves comparing every member of an array with every" 7060 PRINT "other member, using a swap of positions in the array when this is indicated." 7080 PRINT "The prototype of this method is the familar bubblesort. A variation requiring" 7100 PRINT "fewer comparisons involves selecting the last (or first) member of the array." 7120 PRINT "The other members of the array are compared with it, swapping when indicated." 7140 PRINT "This sorts the last member and makes the unsorted array one member shorter each" 7160 PRINT "time the computer runs through the program. Endsort is an example. Any computer" 7180 PRINT "programmer can write other variations.": PRINT 7200 PRINT "Quicksort, taken from the literature, is an example of the next category of" 7220 PRINT "sort procedures. It involves either choosing or finding some value (the value" 7240 PRINT "of the first member of the array in quicksort) as a kind of "; CHR$(34); "fence."; CHR$(34); " The" 7260 PRINT "program then moves all array members with values higher than this fence to the" 7280 PRINT "right side of the array, and all lower values are moved to the left side. The" 7300 PRINT "The fence value then is in its correctly sorted position and need not be" 7320 PRINT "considered further. The array members on the left side, and those on the right" 7340 PRINT "side, are treated as two separate arays. They then are subjected to the sorting" 7345 LOCATE 23, 20: COLOR 15, 1: PRINT "(More. Press any key.)": COLOR 14, 1 7350 IN$ = INPUT$(1) 7355 CLS 7360 PRINT "procedure just described and this process is continued until sorting is" 7380 PRINT "complete.": PRINT 7400 PRINT "I have devised three variations on this theme; I refer to them as jumpsort," 7420 PRINT "flipsort, and fastsort. For long arrays these programs are much faster than" 7440 PRINT "are bubblesort and endsort. It is interesting that removal of a few" 7460 PRINT "unnecessary simple calculations from the commonly written program for quicksort" 7480 PRINT "(stripped quicksort) usually makes this routine a little faster.": PRINT 7500 PRINT "The third group of sort routines is exemplified by the insertion sort, many" 7520 PRINT "variations of which can be written. This sort involves moving an unsorted" 7540 PRINT "member of an array down (or up) the array until it reaches its proper niche:" 7560 PRINT "until the array members lower have smaller values, and the array members higher" 7580 PRINT "have larger values, than that of the inserted member. This type of sort is most" 7600 PRINT "valuable when the problem is to insert and sort new members of an already" 7620 PRINT "sorted array. Under these circumstances, it is very fast.": PRINT 7640 PRINT "The insertion sort can be speeded up for unsorted arrays if the array is" 7660 PRINT "partially sorted in advance of the final sorting by insertion. The Shell-" 7680 PRINT "Metzner sort, taken from the literature, is an example of this. In this" 7700 PRINT "routine, when the variable M becomes 1 (see line 5010 of this program), the" 7705 LOCATE 23, 20: COLOR 15, 1: PRINT "(More. Press any key.)": COLOR 14, 1 7710 IN$ = INPUT$(1) 7712 CLS 7720 PRINT "program then becomes the classical insertion sort, ending when M=0 (see line" 7740 PRINT "5020). I found that the Shell-Metzner sort usually becomes faster if it is" 7760 PRINT "rewritten to yield the routine I call smsort.": PRINT 7780 PRINT "When you run this program for the first time, I suggest you choose 11 from" 7800 PRINT "Menu 2, using an array length of 100." 7820 PRINT : COLOR 15, 1: PRINT TAB(20); "(Press any key to return to Menu 1)": COLOR 14, 1 7840 IN$ = INPUT$(1) 7860 GOTO 10 8000 CLS 8020 FOR X = 1 TO N 8040 FOR Y = 1 TO 4 8060 R = INT(RND * 26): R$ = R$ + CHR$(R + 65) 8080 NEXT Y 8100 A$(X) = R$ 8120 R$ = "" 8130 NEXT X 8150 CLS : PRINT "Unsorted array:": FOR Y = 1 TO N: PRINT A$(Y); " "; : A1$(Y) = A$(Y): NEXT Y: PRINT "" 8160 ON NN GOTO 8200, 8240, 8270, 8300, 8330, 8360, 8390, 8420, 8450, 8480, 8600 8200 T1 = TIMER: GOSUB 9000: T2 = TIMER: SEC1 = T2 - T1: PRINT "Bubblesort:": GOSUB 8900 8210 IF ZZ THEN GOSUB 8920: GOTO 8240 8220 PRINT : PRINT TAB(20); "Bubblesort:"; SEC1; "seconds": GOTO 8940 8240 T1 = TIMER: GOSUB 9500: T2 = TIMER: SEC2 = T2 - T1: PRINT "Endsort:": GOSUB 8900 8250 IF ZZ THEN GOSUB 8920: GOTO 8270 8260 PRINT : PRINT TAB(20); "Endsort:"; SEC2; "seconds": GOTO 8940 8270 T1 = TIMER: GOSUB 10000: T2 = TIMER: SEC3 = T2 - T1: PRINT "Quicksort:": GOSUB 8900 8280 IF ZZ THEN GOSUB 8920: GOTO 8300 8290 PRINT : PRINT TAB(20); "Quicksort:"; SEC3; "seconds": GOTO 8940 8300 T1 = TIMER: GOSUB 10500: T2 = TIMER: SEC4 = T2 - T1: PRINT "Stripped quicksort:": GOSUB 8900 8310 IF ZZ THEN GOSUB 8920: GOTO 8330 8320 PRINT : PRINT TAB(20); "Stripped quicksort:"; SEC4; "seconds": GOTO 8940 8330 T1 = TIMER: GOSUB 11000: T2 = TIMER: SEC5 = T2 - T1: PRINT "Jumpsort:": GOSUB 8900 8340 IF ZZ THEN GOSUB 8920: GOTO 8360 8350 PRINT : PRINT TAB(20); "Jumpsort:"; SEC5; "seconds": GOTO 8940 8360 T1 = TIMER: GOSUB 11500: T2 = TIMER: SEC6 = T2 - T1: PRINT "Flipsort:": GOSUB 8900 8370 IF ZZ THEN GOSUB 8920: GOTO 8390 8380 PRINT : PRINT TAB(20); "Flipsort:"; SEC6; "seconds": GOTO 8940 8390 T1 = TIMER: GOSUB 12000: T2 = TIMER: SEC7 = T2 - T1: PRINT "Fastsort:": GOSUB 8900 8400 IF ZZ THEN GOSUB 8920: GOTO 8420 8410 PRINT : PRINT TAB(20); "Fastsort:"; SEC7; "seconds": GOTO 8940 8420 T1 = TIMER: GOSUB 12500: T2 = TIMER: SEC8 = T2 - T1: PRINT "Insertion sort:": GOSUB 8900 8430 IF ZZ THEN GOSUB 8920: GOTO 8450 8440 PRINT : PRINT TAB(20); "Insertion sort:"; SEC8; "seconds": GOTO 8940 8450 T1 = TIMER: GOSUB 13000: T2 = TIMER: SEC9 = T2 - T1: PRINT "Shell-Metzner sort:": GOSUB 8900 8460 IF ZZ THEN GOSUB 8920: GOTO 8480 8470 PRINT : PRINT TAB(20); "Shell-Metzner sort:"; SEC9; "seconds": GOTO 8940 8480 T1 = TIMER: GOSUB 13500: T2 = TIMER: SEC10 = T2 - T1: PRINT "smsort (rewritten Shell-Metzner):": GOSUB 8900 8490 IF ZZ THEN GOSUB 8920: GOTO 8510 8500 PRINT : PRINT TAB(20); "Smsort (rewritten Shell-Metzner):"; SEC10; "seconds": GOTO 8940 8510 PRINT : PRINT "Bubblesort:"; SEC1; "seconds"; TAB(40); "Endsort:"; SEC2; "seconds" 8520 PRINT "Quicksort:"; SEC3; "seconds"; TAB(40); "Stripped quicksort:"; SEC4; "seconds" 8540 PRINT "Jumpsort:"; SEC5; "seconds"; TAB(40); "Flipsort:"; SEC6; "seconds" 8550 PRINT "Fastsort:"; SEC7; "seconds"; TAB(40); "Insertion sort:"; SEC8; "seconds" 8560 PRINT "Shell-Metzner sort:"; SEC9; "seconds"; TAB(40); "Smsort:"; SEC10; "seconds" 8570 GOTO 8940 8600 ZZ = 1: GOTO 8200 8700 GOTO 10 8890 '*** print sorted array 8900 FOR Y = 1 TO N: PRINT A$(Y); " "; : NEXT Y: PRINT 8910 RETURN 8915 '*** Restore unsorted array 8920 FOR Y = 1 TO N: A$(Y) = A1$(Y): NEXT Y: RETURN 8940 PRINT : PRINT TAB(20); "Press any key to return to the MENU" 8950 I$ = INPUT$(1): RUN 8990 '*** Bubblesort 9000 F = 0 9010 FOR Y = 1 TO N - 1 9020 IF A$(Y) > A$(Y + 1) THEN SWAP A$(Y), A$(Y + 1): F = 1 9030 NEXT Y 9040 IF F = 0 THEN RETURN ELSE F = 0: GOTO 9010 9490 '*** endsort 9500 EN = N + 1 9510 EN = EN - 1 9520 IF EN = 1 THEN RETURN 9530 FOR Y = 1 TO EN - 1 9540 IF A$(Y) > A$(EN) THEN SWAP A$(Y), A$(EN) 9550 NEXT Y 9560 GOTO 9510 9990 '*** quicksort 10000 K8 = 0: I8 = 0 10010 S(I8 + 1) = 1: S(I8 + 2) = N 10020 K8 = K8 + 1 10030 IF K8 = 0 THEN RETURN 10040 K8 = K8 - 1: I8 = K8 + K8 10050 A8 = S(I8 + 1): B8 = S(I8 + 2) 10060 Z8$ = A$(A8): U8 = A8: L8 = B8 + 1 10070 L8 = L8 - 1 10080 IF L8 = U8 THEN 10130 10090 IF Z8$ <= A$(L8) THEN 10070 ELSE A$(U8) = A$(L8) 10100 U8 = U8 + 1 10110 IF L8 = U8 THEN 10130 10120 IF Z8$ >= A$(U8) THEN 10100 ELSE A$(L8) = A$(U8): GOTO 10070 10130 A$(U8) = Z8$ 10140 IF B8 - U8 >= 2 THEN I8 = K8 + K8: S(I8 + 1) = U8 + 1: S(I8 + 2) = B8: K8 = K8 + 1 10150 IF L8 - A8 >= 2 THEN I8 = K8 + K8: S(I8 + 1) = A8: S(I8 + 2) = L8 - 1: K8 = K8 + 1 10160 GOTO 10030 10490 '*** stripped quicksort 10500 K8 = 0 10510 S1(K8) = 1: S2(K8) = N 10520 K8 = K8 + 1 10530 IF K8 = 0 THEN RETURN 10540 K8 = K8 - 1 10550 A8 = S1(K8): B8 = S2(K8) 10560 Z8$ = A$(A8): U8 = A8: L8 = B8 + 1 10570 L8 = L8 - 1 10580 IF L8 = U8 THEN 10630 10590 IF Z8$ <= A$(L8) THEN 10570 ELSE A$(U8) = A$(L8) 10600 U8 = U8 + 1 10610 IF L8 = U8 THEN 10630 10620 IF Z8$ >= A$(U8) THEN 10600 ELSE A$(L8) = A$(U8): GOTO 10570 10630 A$(U8) = Z8$ 10640 IF B8 - U8 >= 2 THEN S1(K8) = U8 + 1: S2(K8) = B8: K8 = K8 + 1 10650 IF L8 - A8 >= 2 THEN S1(K8) = A8: S2(K8) = L8 - 1: K8 = K8 + 1 10660 GOTO 10530 10990 '*** jumpsort 11000 K8 = 0 11010 S1(K8) = 1: S2(K8) = N 11020 K8 = K8 + 1 11030 IF K8 = 0 THEN RETURN 11040 K8 = K8 - 1 11050 A8 = S1(K8): B8 = S2(K8) 11060 Z8$ = A$(A8): U8 = A8: L8 = B8 + 1 11070 L8 = L8 - 1 11080 IF L8 = U8 THEN 11130 11090 IF Z8$ <= A$(L8) THEN 11070 ELSE SWAP A$(U8), A$(L8) 11100 U8 = U8 + 1 11110 IF L8 = U8 THEN 11130 11120 IF Z8$ >= A$(U8) THEN 11100 ELSE SWAP A$(L8), A$(U8): GOTO 11070 11130 IF B8 - U8 >= 2 THEN S1(K8) = U8 + 1: S2(K8) = B8: K8 = K8 + 1 11140 IF L8 - A8 >= 2 THEN S1(K8) = A8: S2(K8) = L8 - 1: K8 = K8 + 1 11150 GOTO 11030 11490 '*** flipsort 11500 C = 0 11510 B1(C) = 1: B2(C) = N 11520 C = 1 11530 IF C = 0 THEN RETURN 11540 C = C - 1: D = B1(C): E = B2(C) 11550 F = D - 1: G = E 11560 F = F + 1 11570 IF F = G THEN 11620 11580 IF A$(F) > A$(G) THEN SWAP A$(F), A$(G) ELSE 11560 11590 G = G - 1 11600 IF F = G THEN 11620 11610 IF A$(G) < A$(F) THEN SWAP A$(G), A$(F): GOTO 11560 ELSE 11590 11620 IF E - F >= 2 THEN B1(C) = F + 1: B2(C) = E: C = C + 1 11630 IF G - D >= 2 THEN B1(C) = D: B2(C) = G - 1: C = C + 1 11640 GOTO 11530 11990 '*** fastsort 12000 C = 0 12010 B1(C) = 1: B2(C) = N 12020 C = C + 1 12030 IF C = 0 THEN RETURN 12040 C = C - 1 12050 D = B1(C): E = B2(C) 12060 Z$ = A$(D): F = D - 1: G = E + 1 12070 FOR Y = D TO E 12080 IF Z$ > A$(Y) THEN F = F + 1: A$(F) = A$(Y) 12090 IF Z$ < A$(Y) THEN G = G - 1: A2$(G) = A$(Y) 12100 NEXT Y 12110 FOR Y = G TO E: A$(Y) = A2$(Y): NEXT Y 12120 FOR Y = F + 1 TO G - 1: A$(Y) = Z$: NEXT Y 12130 IF F - D > 0 THEN B1(C) = D: B2(C) = F: C = C + 1 12140 IF E - G > 0 THEN B1(C) = G: B2(C) = E: C = C + 1 12150 GOTO 12030 12490 '*** insertion sort 12500 FOR Y = 1 TO N - 1 12510 IF A$(Y) > A$(Y + 1) THEN SWAP A$(Y), A$(Y + 1) ELSE 12550 12520 D = Y - 1: IF D < 1 THEN 12550 12530 IF A$(D) > A$(D + 1) THEN SWAP A$(D), A$(D + 1) ELSE 12550 12540 D = D - 1: IF D >= 1 THEN 12530 12550 NEXT Y 12560 RETURN 12990 '*** Shell-Metzner sort 13000 M = N 13010 M = INT(M / 2) 13020 IF M = 0 THEN RETURN 13030 K = N - M: J = 1 13040 I = J 13050 L = I + M 13060 IF A$(I) <= A$(L) THEN 13100 13070 SWAP A$(I), A$(L): I = I - M 13090 IF I >= 1 THEN 13050 13100 J = J + 1 13110 IF J <= K THEN 13040 ELSE 13010 13490 '*** smsort (rewritten Shell-Metzner) 13500 M = N 13510 M = INT(M / 2): K = N - M 13520 IF M = 0 THEN RETURN 13530 FOR Y = 1 TO K 13540 IF A$(Y) > A$(Y + M) THEN SWAP A$(Y), A$(Y + M) ELSE 13580 13550 D = Y - M: IF D < 1 THEN 13580 13560 IF A$(D) > A$(D + M) THEN SWAP A$(D), A$(D + M) ELSE 13580 13570 D = D - M: IF D >= 1 THEN 13560 13580 NEXT Y 13590 GOTO 13510